//输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 
//
// 要求时间复杂度为O(n)。 
//
// 
//
// 示例1: 
//
// 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 
//
// 
//
// 提示： 
//
// 
// 1 <= arr.length <= 10^5 
// -100 <= arr[i] <= 100 
// 
//
// 注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/ 
//
// 
//
// Related Topics 数组 分治 动态规划 👍 714 👎 0


package leetcode.editor.cn;

class 连续子数组的最大和 {
    public static void main(String[] args) {
        Solution solution = new 连续子数组的最大和().new Solution();
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4,12,3,2,-4,-2,7};
        System.out.println(solution.maxSubArray(nums));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        int[] nums;

        public class Status {
            public int lSum, rSum, mSum, iSum;
            public Status(int lSum, int rSum, int mSum, int iSum) {
                this.lSum = lSum;
                this.rSum = rSum;
                this.mSum = mSum;
                this.iSum = iSum;
            }
        }

        public int maxSubArray(int[] nums) {
            this.nums = nums;
            return merge(0, nums.length - 1).mSum;
        }

        public Status merge(int l, int r) {
            if (l == r) {
                return new Status(nums[l], nums[l], nums[l], nums[l]);
            }
            int mid = l + ((r - l) >> 1);
            Status left = merge(l, mid);
            Status right = merge(mid + 1, r);
            return new Status(Math.max(left.lSum,left.iSum + right.lSum),
                    Math.max(right.rSum,right.iSum + left.rSum),
                    Math.max(left.rSum+right.lSum,Math.max(left.mSum,right.mSum)),
                    left.iSum+right.iSum);
        }


        public int maxSubArray1(int[] nums) {
            int pre = 0, max = nums[0];
            for (int num : nums) {
                pre = Math.max(pre + num, num);
                max = Math.max(max, pre);
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
